package Tree;

import java.util.Map;

public class leet_110 {

}

class Solution_110 {
    public boolean isBalanced(TreeNode root) {
        boolean result = func1(root);
        return result;
    }

    /**
     * 直接判断
     * @param root
     * @return
     */
    public boolean func1(TreeNode root){
        if(root==null){return true;}
        boolean flag = false;
        int rightLevel = height(root.right);
        int leftLevel = height(root.left);
        if(Math.abs(rightLevel-leftLevel)<=1){
            flag = true;
        }
        return flag && func1(root.left) && func1(root.right);
    }

    public int height(TreeNode root){
        if(root==null){
            return 0;
        }
        if(root.right==null && root.left==null){
            return 1;
        }
        return 1+Math.max(height(root.left), height(root.right));
    }


    /**
     * 去除重复判断 如果在寻找过程中发现了不为平衡二叉树直接返回
     * @param root
     * @return
     */
    public boolean func2(TreeNode root){
        int result = height2(root);
        if(result==-1){
            return false;
        }
        return true;
    }

    public int height2(TreeNode root){
        if(root==null){return 0;}
        int heightLeft = height2(root.left);
        if(heightLeft==-1){return -1;}

        int heightRight = height2(root.right);
        if(heightRight==-1){return -1;}

        int height=Math.abs(heightLeft-heightRight);
        if(height>1){
            return -1;
        }

        return 1+Math.max(heightLeft, heightRight);
    }
}
